High Efficiency Video Coding (HEVC) is a new coding standard that has been developed in recent years. In the High Efficiency Video Coding (HEVC) system, the fixed-size macroblock of H.264/AVC is replaced by a flexible block, named coding unit (CU). Pixels in the CU share the same coding parameters to improve coding efficiency. A CU may begin with a largest CU (LCU), which is also referred as coded tree unit (CTU) in HEVC. In addition to the concept of coding unit, the concept of prediction unit (PU) is also introduced in HEVC. Once the splitting of CU hierarchical tree is done, each leaf CU is further split into one or more prediction units (PUs) according to prediction type and PU partition.
Along with the High Efficiency Video Coding (HEVC) standard development, the development of extensions of HEVC has also started. The HEVC extensions include screen content coding (SCC). Due to specific characteristics of screen contents, coding tools have been developed and demonstrate significant gains in coding efficiency. Among them, the color index coding (a.k.a. major color based coding) techniques represent block of pixels using indices to the palette (major colors), and encode the palette and the indices by exploiting spatial redundancy. While the total number of possible color combinations is huge, the number of colors in an area of picture is usually very limited for typical screen contents. Therefore, the color index coding becomes very effective for screen content materials. Related key color index coding techniques are briefly reviewed as follows.
Major-Color-Based Screen Content Coding
The major-color-based screen content coding is disclosed in JCTVC-O0108 (Guo, et al., “RCE4: Test1. Major-color-based screen content coding”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 16th Meeting: San Jose, Calif., USA, Jan. 9-17, 2014, Document: JCTVC-P0108). Major-color-based screen content coding is performed on a CU basis. The encoding process is as follows:
Selecting Major Colors
A very simple but efficient histogram based algorithm is used to classify the pixels. In specific, the most significant L peak values in the histogram are selected as major colors, and the pixel values that are close to a major color will be quantized to the major color. Other pixels which do not belong to any major color sets are escape pixels, which will also be quantized before coding. For lossless coding, both of the quantization processes are not used. For each pixel, a color index is assigned to indicate which color set it belongs to. The color index may also be referred as an index for convenience when the term will not cause any confusion. If L major colors are used, the values of major colors 0 to (L−1) are signaled for the set of L major colors and the value of major color N is signaled for the escape pixel set.
Encoding the Color Index
After classification, the pixels of a block can be converted into color indices according to the major color set selected. A predictive coding method is applied to the indices, where a pixel line can be predicted by three different modes, including horizontal mode (i.e., copy index mode), vertical mode (i.e., copy above mode) and normal mode (i.e., escape mode).
Copy Index Mode
In copy index mode, starting from the first pixel, one or more consecutive indices are copied from the first pixel. The index of the first pixel is signaled.
Copy Above Mode
In this mode, one or more consecutive indices are copied from above pixel line.
Escape Mode
When an escape pixel is encountered (signaled by the largest index in major color set), its corresponding pixel value is coded right after the index. There may be more than 1 escape pixels and in different color values in the CU. For different escape pixel locations, the pixel values of escape pixels may be different.
Palette Mode Coding
A palette-based coding technique is disclosed in JCTVC-P0198 (Guo et al., “RCE4: Results of Test 2 on Palette Mode for Screen Content Coding”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 16th Meeting: San Jose, Calif., USA, Jan. 9-17, 2014, Document: JCTVC-P0198). The palette-based coding is performed on a CU basis. The encoding process is as follows:
Transmission of the Palette:
the palette size is first transmitted followed by the palette elements. The maximum palette size is set to 24.
Transmission of Pixel Values:
the pixels in the CU are encoded in a raster scan order. For each position, a flag is first transmitted to indicate whether the “run mode” (i.e., “copy-index mode” in this disclosure) or “copy-above mode” is being used.
“Run mode”: In “run mode” (i.e., “copy-index mode” in this disclosure), a palette index is first signaled followed by “palette_run” (e.g., M). No further information needs to be transmitted for the current position and the following M positions as they have the same palette index as signaled. The palette index (e.g., i) is shared by all three color components, which means that the reconstructed pixel values are (Y, U, V)=(paletteY[i], paletteU[i], paletteV[i]) if the color space corresponds to YUV.
“Copy-Above Mode”:
In “copy-above mode”, a value “copy_run” (e.g., N) is transmitted to indicate that for the following N positions (including the current one), the palette index is equal to the palette index of the one that is at the same location in the row above.
Transmission of Residue:
the palette indices transmitted are converted back to pixel values and used as the prediction. Residue information is transmitted using HEVC residue coding and is added to the prediction for the reconstruction.
Copy from Previous Row Above
Another index coding mode, called “copy from previous row”, is disclosed in JCTVC-R0202 (Zou et al., “Non-SCCE3: Copy from previous row mode for palette coding”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 18th Meeting: Sapporo, Japan, Jun. 30-Jul. 9, 2014, Document: JCTVC-R0202). This method enables to copy pixels from previously coded rows beyond the row above in the current CU. To achieve a better coding efficiency, all the previous coded rows are available as reference according to JCTVC-R0202. Accordingly, this mode is called “copy from previous row”. This mode is added in the available palette mode candidate list. The row index information is coded when the current string chooses “copy from previous row” mode. The row index is coded using truncated binary codeword. Basically, a shorter codeword is designed for the row which is near to the current row. Similar to other modes, the matching length is coded in the bitstream.
In JCTVC-O0108 and JCTVC-P0198, similar palette based coding methods are disclosed. These references use slightly different terms for related parameters. The term “palette” in JCTVC-O0108 and the term “major color sets” in JCTVC-P0198 is referred as “major color table” in this disclosure. The term “palette index” in JCTVC-O0108 and the term “color index” in JCTVC-P0198 are referred as “color index” in this disclosure. The color indices related to the current coding unit are referred as “index map”.
For a run of indices in the index map, there are several elements that need to be signaled, including:                1) Run type: either it is a copy above run or a copy index run.        2) Palette index: in a copy index run, it is used to signal what index is used for this run.        3) Run length: the length of this run for both copy above and copy index type.        4) Escape pixel: if there N (N>=1) escape pixels in the run, the N pixel values need to be signaled for these N escape pixels.        
In JCTVC-T0065 (Karczewicz, et al., Non CE1: Grouping Palette Indices At Front, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 20th Meeting: Geneva, CH, 10-18 Feb. 2015, Document: JCTVC-T0065), a syntax signaling is disclosed, where all the palette indices are grouped together. The number of palette indices is signaled first, following by the palette indices.
The coding of palette index run type and run length in the HEVC Screen Content Coding specification (Joshi, et al., High Efficiency Video Coding (HEVC) Screen Content Coding: Draft 2, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 19th Meeting: Strasbourg, FR, 17-24 Oct. 2014, Document: JCTVC-S1005) is as follows:
TABLE 1Noteif( indexMax > 0 && scanPos > = nCbS &&palette_run_type_flag[ xcPrev ][ ycPrev ]! = COPY_ABOVE_MODE ) {palette_run_type_flag[ xC ][ yC ](1-1)}if( palette_run_type_flag[ xC ][ yC ] = =COPY_INDEX_MODE &&adjustedIndexMax > 0)palette_index_idc(1-2)if( indexMax > 0 ) {maxPaletteRun = nCbS * nCbS − scanPos − 1if( maxPaletteRun > 0 ) {palette_run_msb_id_plus1(1-3)if( palette_run_msb_id_plus1 > 1 )palette_run_refinement_bits(1-4)}
As shown in Table 1, syntax elements for the palette run type (i.e., palette_run_type_flag[xC][yC]) and palette index (i.e., palette_index_idc) are incorporated for each occurrence as indicated by Notes (1-1) and (1-2). Two syntax elements palette_run_msb_id_plus1 and palette_run_refinement_bits are used to signal the run length corresponding to a MSB (most significant bit) part and refinement part respectively as indicated by Notes (1-3) and (1-4) in Table 1.
During the Course of Screen Content Coding (SCC) development, various video coding tools have been described, including the “Intra picture block copy” (IntraBC) technique. The IntraBC technique was first disclosed in JCTVC-M0350 (Budagavi et al., AHG8: Video coding using Intra motion compensation, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG16 WP3 and ISO/IEC JTC 1/SC 29/WG11 13th Meeting: Incheon, KR, 18-26 Apr. 2013, Document: JCTVC-M0350). An example according to JCTVC-M0350 is shown in FIG. 1, where a current coding unit (CU, 110) is coded using Intra MC (motion compensation). The prediction block (120) is located from the current CU and a displacement vector (112). In this example, the search area is limited to the current CTU (coding tree unit), the left CTU and the left-left CTU. The prediction block is obtained from the already reconstructed region. Then, the displacement vector, also named motion vector (MV) or block vector (BV), and residual for the current CU are coded. It is well known that the HEVC adopts CTU and CU block structure as basic units for coding video data. Each picture is divided into CTUs and each CTU is reclusively divided into CUs. During prediction phase, each CU may be divided into multiple blocks, named prediction units (PUs) for performing prediction process.
In JCTVC-M0350, the IntraBC is different from the motion compensation used for Inter prediction in at least the following areas:                BVs are restricted to be 1-D for IntraBC (i.e., either horizontal or vertical) while Inter prediction uses 2-D motion estimation.        Binarization is fixed length for IntraBC while Inter prediction uses exponential-Golomb.        IntraBC introduces a new syntax element to signal whether the BV is horizontal or vertical.        
Based on JCTVC-M0350, some modifications are disclosed by Pang, et al., in Non-RCE3: Intra Motion Compensation with 2-D MVs, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 14th Meeting: Vienna, AT, 25 Jul. 2-Aug. 2013, Document: JCTVC-N0256 (hereinafter JCTVC-N0256). Firstly, the IntraBC is extended to support 2-D MVs, so that both vertical and horizontal MV components can be non-zero at the same time. This provides more flexibility to IntraBC than the original approach, where the MV is restricted to be strictly horizontal or vertical.
In JCTVC-N0256, two BV coding methods are disclosed:                Method 1—Block vector prediction. The left or above BV is selected as the BV predictor and the resulting motion vector difference (BVD) is coded. A flag is used to indicate whether the BVD is zero. When BVD is not zero, exponential-Golomb codes of the 3rd order are used to code the remaining absolute level of the BVD. Another flag is used to code the sign.        Method 2: No block vector prediction. The BV is coded using the exponential-Golomb codes that are used for BVD in HEVC.        
Another difference disclosed in JCTVC-N0256 is that the 2-D IntraBC is further combined with the pipeline friendly approach:                1. No interpolation filters are used.        2. BV search area is restricted. Two cases are disclosed:                    a. Search area is the current CTU and the left CTU or            b. Search area is the current CTU and the rightmost 4 column samples of the left CTU.                        
Among the proposed methods in JCTVC-N0256, the 2-D IntraBC, the removal of interpolation filters, and the search area constraint to the current CTU and the left CTU have been adopted in a draft HEVC SCC standard.
The decoding and parsing process according to JCTVC-R1005 are briefly described as follows.                1. Signaling of the palette:                    1.1 Signal ‘palette sharing flag’ first which indicates palette predictor is used as the current palette. If it is true, the following process in steps 1.2 to 1.4 is skipped.            1.2 Signal ‘reused flag's indicate which elements of palette predictor are used in current palette.            1.3 Signal ‘number of non-predicted elements’ which indicate how many elements in current palette are not predicted from palette predictor.            1.4 Signal value of each non-predicted element.                        2. Signaling of the color index map:                    2.1 The pixels in the block can be coded in horizontally raster scan order, vertically raster order, horizontally traverse scan order and vertically traverse order.            2.2 For each position, a flag is first transmitted to indicate which prediction mode between ‘copy above mode’ and ‘new run mode’ is being used.            2.3 When ‘copy above mode’ is used, ‘number of runs’ follows the flag. For the number of runs the indices are same as those in above line along the scan order            2.4 When ‘new run mode’ is used, ‘index’ is signaled after the flag.                            2.4.1 When the ‘index’ is ‘ESCAPE’, the pixel value itself is signaled.                2.4.2 When the ‘index’ is in the palette table, ‘number of runs’ is signaled. For the number of runs the indices are same as the index signaled.                                                
In the existing palette coding practice, the palette coding is always applied to underlying video data with multi-color formats, such as YUV or RGB. There is no mentioning regarding palette coding for the monochrome video data. It is desirable to develop techniques of palette coding for monochrome video data.